/**
 * 
 */
package array.passed;

/**
 * @author xyyi
 *
 */
public class MedianofTwoSortedArrays {

	/**
	There are two sorted arrays A and B of size m and n respectively. 
	Find the median of the two sorted arrays. 
	The overall run time complexity should be O(log (m+n)).
	 */

	/**
	 * Solution 1 Sort
	 * Copy 2 array to 3rd array and sort it 
	 * time O( (m+n)log(m+n)  )
	 * space O(m + n)
	 */

	/**
	 * Solution 2 Merge
	 * Use merge method in merge sort, just keep 2 pointer to this 2 sorted array and compare one by one
	 * time O(m+n)
	 * space O(m + n)
	 */

	/**
	 * Solution 3 Comparing median
	 * 
	 * time O(log(m+n))
	 * space O(1)
	 */

	/**
	 * Solution 4 Find median
	 * A[m]    3 5 7     
	 *           i
	 * B[n]    2 4 6 8 10
	 *          j
	 *  i = m / 2;
	 *  j = (m + n) / 2 - i      
	 * time O(log(m+n))
	 * space O(1)
	 */

	public double findMedianSortedArraysON(int A[], int B[]) {
		// Start typing your Java solution below
		// DO NOT write main() function        

		int total = A.length + B.length;
		int count = total / 2;
		int ai = 0, bi = 0;
		int last = 0;
		int median = 0;
		while (count >= 0 && ai < A.length && bi < B.length) {
			last = median;
			if (A[ai] < B[bi]) {
				median = A[ai];
				ai++;
			} else {
				median = B[bi];
				bi++;
			}
			count--;
		}

		if (count >= 0) {
			if (count == 0) {
				last = median;
			} else {
				if (ai == A.length) {
					last = B[bi + count - 1];
				} else {
					last = A[ai + count - 1];
				}
			}

			if (ai == A.length) {
				median = B[bi + count];
			} else {
				median = A[ai + count];
			}
		}

		return total % 2 == 1 ? median : (last + median) / 2;
	}

	/**
	 * Using find kth smllest in 2 sorted array to get median of 2 sorted array
	 * 2 sorted array A[n] B[m]
	 * case 1 if m + n is odd, findkthSmallest((m+n) / 2)
	 * case 2 if m + n is even, (findkthSmallest( (m+n) / 2 ) +findkthSmallest( (m+n)/2 + 1 )) / 2
	 * lg(k) where k = (m + n) / 2
	 */
	public double findMedianSortedArrays(int A[], int B[]) {
		int size = A.length + B.length;
		if ((size & 0x1) == 1) {// odd number of element
			return findKthSmallest(A, 0, B, 0, size / 2 + 1);
		} else {
			return (findKthSmallest(A, 0, B, 0, size / 2) + findKthSmallest(A,
					0, B, 0, size / 2 + 1)) / 2.0;
		}
	}

	/*
	 * Best for interview
	 * recursive
	 */
	int findKthSmallest(int[] A, int ai, int[] B, int bi, int k) {
		if (B.length - bi < A.length - ai) {
			return findKthSmallest(B, bi, A, ai, k);
		}
		if (ai == A.length) {
			return B[bi + k - 1];
		}
		if (k == 1) {
			return Math.min(A[ai], B[bi]);
		}

		int stepA = Math.min(k / 2, A.length - ai);
		int stepB = k - stepA;
		if (A[ai + stepA - 1] < B[bi + stepB - 1]) {
			return findKthSmallest(A, ai + stepA, B, bi, k - stepA); // k > stepA, cannot be 0
		} else {
			return findKthSmallest(A, ai, B, bi + stepB, k - stepB); //k > stepB, cannot be 0
		}
	}

	int findKthSmallestIterative(int[] A, int ai, int[] B, int bi, int k) {
		while (true) {
			if (B.length - bi < A.length - ai) {
				int i = ai;
				ai = bi;
				bi = i;
				int[] arr = A;
				A = B;
				B = arr;
			}

			if (A.length == ai) {
				return B[bi + k - 1];
			}
			if (k == 1) {
				return Math.min(A[ai], B[bi]);
			}
			int stepA = Math.min(k / 2, A.length - ai);
			int stepB = k - stepA;
			if (A[ai + stepA - 1] < B[bi + stepB - 1]) {
				ai += stepA;
				k -= stepA;
			} else {
				bi += stepB;
				k -= stepB;
			}
		}
	}

	/*
	int findKthSmallest(int a[], int m, int b[], int n, int k) {
		if( n > m )  return findKthSmallest(b,n,a,m,k);
	          //维持 b[n]是短数组， 维持n ≤ m
		if( n == 0) return a[k-1];
		if( k == 1) return min(a[0],b[0]);

		int pb = min(k/2, n);   
		int pa = k - pb;         
		if(a[pa-1] > b[pb-1]) 
	         return findKthSmallest(a,m,b+pb,n-pb,k-pb);   //k-pb>0，取不到0
		else 
	         return findKthSmallest(a+pa,m-pa,b,n,k-pa);   //k-pa>0，取不到0

	}
	*/

	// http://leetcode.com/2011/01/find-k-th-smallest-element-in-union-of.html
	// log(m + n)
	public double findMedianSortedArraysCompareMiddle(int A[], int B[]) {
		int size = A.length + B.length;
		if ((size & 0x1) == 1) {// odd number of element
			return findMedianSortedArraysCompareMiddleHelper(A, 0, A.length, B,
					0, B.length, size / 2 + 1);
		} else {
			return (findMedianSortedArraysCompareMiddleHelper(A, 0, A.length,
					B, 0, B.length, size / 2) + findMedianSortedArraysCompareMiddleHelper(
					A, 0, A.length, B, 0, B.length, size / 2 + 1)) / 2.0;
		}
	}

	int findMedianSortedArraysCompareMiddleHelper(int[] A, int a0, int sizeA,
			int[] B, int b0, int sizeB, int k) {

		int i = (int) ((double) sizeA / (sizeA + sizeB) * (k - 1));
		int j = k - 1 - i;

		int ai_1 = (i == 0) ? Integer.MIN_VALUE : A[a0 + i - 1];
		int bj_1 = (j == 0) ? Integer.MIN_VALUE : B[b0 + j - 1];
		int ai = (i == sizeA) ? Integer.MAX_VALUE : A[a0 + i];
		int bj = (j == sizeB) ? Integer.MAX_VALUE : B[b0 + j];

		if (bj_1 <= ai && ai <= bj)
			return ai;
		if (ai_1 <= bj && bj <= ai)
			return bj;

		if (ai < bj) {
			return findMedianSortedArraysCompareMiddleHelper(A, a0 + i + 1,
					sizeA - i - 1, B, b0, j, k - i - 1);
		} else { // bj < ai
			return findMedianSortedArraysCompareMiddleHelper(A, a0, i, B, b0
					+ j + 1, sizeB - j - 1, k - j - 1);
		}
	}

	// ####################     #########################
	public double findMedianSortedArraysM(int a[], int b[]) {
		// Start typing your Java solution below
		// DO NOT write main() function
		return findMedian(a, 0, a.length, b, 0, b.length);
	}

	private double findMedian(int[] a, int a0, int m, int[] b, int b0, int n) {
		if ((m + n) % 2 == 0)
			return (findK(a, a0, m, b, b0, n, (m + n) / 2) + findK(a, a0, m, b,
					b0, n, (m + n) / 2 + 1)) / 2;
		else
			return findK(a, a0, m, b, b0, n, (m + n) / 2 + 1);
	}

	private double findK(int[] a, int a0, int m, int[] b, int b0, int n, int k) {
		System.out.println("a0:" + a0 + ",m:" + m + ",b0:" + b0 + ",n:" + n
				+ ",k:" + k);
		if (m <= 0)
			return b[b0 + k - 1];
		if (n <= 0)
			return a[a0 + k - 1];
		if (k <= 1)
			return Math.min(a[a0], b[b0]);
		if (a[a0 + m / 2] >= b[b0 + n / 2]) {
			if (m / 2 + n / 2 >= k - 1)
				return findK(a, a0, m / 2, b, b0, n, k);
			else
				return findK(a, a0, m, b, b0 + n / 2 + 1, n - n / 2 - 1, k - n
						/ 2 - 1);
		} else {
			if (m / 2 + n / 2 >= k - 1)
				return findK(a, a0, m, b, b0, n / 2, k);
			else
				return findK(a, a0 + m / 2 + 1, m - m / 2 - 1, b, b0, n, k - m
						/ 2 - 1);
		}
	}

	/**
	 * 
	 */
	public MedianofTwoSortedArrays() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		//		int[] a = { 1, 2, 3, 5, 6, 94 };
		//		int[] b = { 4, 7, 8 };
		int[] a = { 1 };
		int[] b = { 1 };
		MedianofTwoSortedArrays mta = new MedianofTwoSortedArrays();
		System.out.println(mta.findMedianSortedArraysCompareMiddle(a, b));
	}

}
